# https://leetcode-cn.com/problems/delete-operation-for-two-strings/
# 583.两个字符串的删除操作

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        result = 0

        dp = [[0 for i in range(n2 + 1)] for i in range(n1 + 1)]
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                result = max(result, dp[i][j])

        return n1 + n2 - result * 2
